User blog:LittlePeng9/Functions between computability and busy beaver
Warning: I'm going to use concepts from computability theory which I'm not going to describe in great detail (mainly Turing degrees), so if interested, I recommend first of all checking out what the idea behind Turing degree is, and for other things feel free to ask in comments. So, I have recently been wondering, is it possible to have a function \(F\) which is, in fundamental way, inbetween all computable functions and the busy beaver function (for simplicity, let it be \(S(n)\)). Turns out, as expected, that the answer depends on what we precisely mean with "fundamentally between". There is quite intuitive notion for this, but I'd rather go about making it more formal. First, I want my function to be above all computable functions. Two most obvious formalizations for this intuitive notion are: *\(F\) dominates all computable functions, which means that for any computable function \(f\) and sufficiently large \(n\) we have \(F(n)>f(n)\). *\(F\) isn't bounded by any any computable function, i.e. no computable function \(f\) satisfies, for all \(n\), \(F(n)S(n)\) we have \(f(n)>0'(n)\). Now, there is a theorem, proof of which I don't understand fully, which says that the above is enough for the degree to be array nonrecursive, you can find the proof here. The idea is that if, to compute function \(g\leq_\text{wtt}0'\) we need at most \(h(n)\) oracle queries to \(0'\) for computable \(h\) (which exists by definition of wtt-reducibility), then we can "approximate" \(0'\) by using the fact that \(f(h(n+1))>0'(h(n))\) for infinitely many \(n\), and for these we can exceed \(g(n)\). Thanks to this, we reach a contradiction with choice of \(A\). So \(S\) eventually dominates \(f\) for every \(f\) which is \(F\)-computable. Now suppose \(F\) was bounded by some computable function \(f\), so that \(f(n)>F(n)\) for all \(n\). If we know that \(a\) doesn't take value \(n\) for first \(f(n)\), then surely it doesn't for first \(F(n)\), so, by definition of \(F\), it means that \(a\) will never take value \(n\), so \(n\not\in A\). So we can decide membership in \(A\) by computing first \(f(n)\) values of \(a\) and looking for \(n\) there. This however stands in contradiction with choice of \(A\) to be nonrecursive. So indeed \(F\) isn't bounded by any computable function. Another case which is of interest is a function which dominates all recursive functions, but no recursive extension of it can bound \(S\). For this, choose any set \(A\) which is recursively enumerable, Turing-incomplete and has high degree (i.e. \(A'\equiv_T 0' '\)) (such degree exists, again, priority methods). By Martin's domination theorem, there exists an \(A\)-computable function \(F\) which dominates all computable functions. Suppose that some recursive extension \(f\) of this function bounds \(S\). Then we know that if \(n\)-state Turing machine works for more than \(f(n)\) steps, then it cannot halt (by definition of \(S\)). So we can decide the halting problem, which is a contradiction, because we assumed \(A\) cannot decide \(0'\). Fourth case, a function which isn't bounded by computable function and doesn't recursively bound \(S\), follows as a possibility from either of the above two. Category:Blog posts